package com.yww.leetcode.heap;

import com.yww.datastructure.heap.Heap;

/**
 * @author yww
 * @description 215. 数组中的第K个最大元素
 * @since 2024/2/7 21:40
 */
public class FindKthLargest215 {
    // 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
    //请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

    /**
     * 解题思路
     * <p>
     * 1. 向小顶堆放入前k个元素
     * 2. 剩余元素
     * 1. 若 <= 堆顶元素，则略过
     * 2. 若 > 堆顶元素，则替换堆顶元素
     * 3. 这样小顶堆始终保留的是目前为止，前 k 大 的元素
     * 4. 循环结束，堆顶元素即为 第 K 大 元素
     */
    public int findKthLargest(int[] nums, int k) {
        Heap minHeap = new Heap(false, k);
        for (int i = 0; i < k; i++) {
            minHeap.offer(nums[i]);
        }
        for (int i = k; i < nums.length; i++) {
            if (minHeap.peek() < nums[i]) {
                minHeap.replace(nums[i]);
            }
        }
        return minHeap.peek();
    }
}
